/**
      <one line to give the program's name and a brief idea of what it does.>
    Copyright (C) <2011>  <André Mendes de Oliveira Paiva>

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  
 */

package estrutura.lista;

import estrutura.EstruturaDados;
import estrutura.No;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;

public class ListaEstatica extends EstruturaDados {

    private NoLista[] vertices;

    public ListaEstatica(String nome, int qtdeNo) {
        super(nome, qtdeNo);
        vertices = new NoLista[this.getQtdeNo()];
    }

    public ListaEstatica(String nome) {
        this(nome, QTDE_MAX_NO);
    }

    public ListaEstatica(int qtdeNo) {
        this(NOME_ESTRUTURA_ANONIMA, qtdeNo);
    }

    public ListaEstatica() {
        this(NOME_ESTRUTURA_ANONIMA, QTDE_MAX_NO);
    }

    private int obterMaxId()
    {
        int maxId = 0;
        for (NoLista no : vertices)
        {
            if (no == null) break;
            if (no.getId() > maxId) {
                maxId = no.getId();
            }
        }
        return maxId;
    }
    
    @Override
    public boolean inserirNo(String valor) {
        boolean ret = false;
        int i;
        /* Procura pelo primeiro idNoice disponivel no vetor */
        for (i = 0; i < vertices.length; i++) {
            /* quando encontrar o idNo disponível sai do looping */
            if (vertices[i] == null) {
                break;
            }
        }
        /*
          se chegou até o fim do looping (fim do vetor) e o vetor já atingiu i
          tamanho máximo, então retorna false
         */
        if (i < this.getQtdeNo()) {
            /* Cria o nó e adiciona-o ao vetor de vertices */
            NoLista novoNo = new NoLista(this.obterMaxId()+1, valor);
            vertices[i] = novoNo;
            ret = true;
        }
        return ret;
    }

    
    /* Otem um determinado no a partir do ID do Nó */
    public NoLista obterNo(int idNo) {
        NoLista no = null;
        /* Pesquisa o ID do Nó */
        for (int i = 0; i < vertices.length; i++) {
            if (vertices[i] != null && vertices[i].getId() == idNo) {
                no = vertices[i];
                break;
            }
        }
        /* Verifica se a posição do vetor contem um nó válido */
        if (no == null) {
            System.out.println("O ID [" + idNo + "] nao existe.");
        }
        return no;
    }

    /* Otem o indice de um determinado no a partir do ID do Nó */
    @Override
    public int obterIndiceNo(int idNo) {
        int i;
        /* Pesquisa o ID do Nó */
        for (i = 0; i < vertices.length; i++) {
            if (vertices[i] != null && vertices[i].getId() == idNo) {
                break;
            }
        }
        if (i == vertices.length) {
            i = -1;
        }
        return i;
    }

    public ArestaLista obterAresta(int idNoOrigem, int idNoDestino) {
        ArestaLista aresta = null;
        NoLista noOrigem = this.obterNo(idNoOrigem);
        if (noOrigem != null) {
            aresta = noOrigem.obterAresta(idNoDestino);
        }
        noOrigem = null;
        return aresta;
    }

    @Override
    public boolean inserirAresta(int idNoOrigem, int idNoDestino) {
        return inserirAresta(idNoOrigem, idNoDestino, null);
    }

    @Override
    public boolean inserirAresta(int idNoOrigem, int idNoDestino, Object rotulo) {
        return this.inserirAresta(idNoOrigem, idNoDestino, rotulo, 0);
    }
    
    public boolean inserirAresta(int idNoOrigem, int idNoDestino, Object rotulo, int peso) {
        /* verifica se existe aresta */
        boolean ret = false;
        NoLista noOrigem = this.obterNo(idNoOrigem);
        NoLista noDestino = this.obterNo(idNoDestino);
        if (noOrigem != null && noDestino != null) {
            ret = noOrigem.addAresta(noDestino, rotulo, peso);
        }
        noOrigem = null;
        noDestino = null;
        return ret;
    }
    @Override
    public boolean inserirRotulo(int idNoOrigem, int idNoDestino, Object rotulo) {
        boolean ret = false;
        NoLista noOrigem = this.obterNo(idNoOrigem);
        if (noOrigem != null) {
            ret = noOrigem.addRotulo(idNoDestino, rotulo);
        }
        return ret;
    }
    @Override
    public boolean excluirNo(int idNo) {
        boolean ret = false;
        int indNo = this.obterIndiceNo(idNo);
        if (indNo != -1) {
            ret = true;
            NoLista no = this.obterNo(idNo);
            /* remove todas as arestas */
            no.removeAllAresta();
            /* exclui as Arestas dos outros nós que tenham ligação com este nó  */
            for (int i = 0; i < vertices.length; i++) {
                /* Se não for o mesmo Nó, então chama rotina para exclui A aresta com este nó */
                if (vertices[i] != null && vertices[i].getId() != idNo) {
                    vertices[i].removeAresta(idNo);
                }
            }
            /* exclui o nó */
            vertices[indNo] = null;
        }
        return ret;
    }

    @Override
    public boolean excluirRotulo(int idNoOrigem, int idNoDestino) {
        /* verifia se existe aresta */
        boolean ret = false;
        NoLista noOrigem = this.obterNo(idNoOrigem);
        if (noOrigem != null) {
            ret = noOrigem.removeRotulo(idNoDestino);
        }
        return ret;
    }

    @Override
    public boolean excluirAresta(int idNoOrigem, int idNoDestino) {
        /* verifia se existe aresta */
        boolean ret = false;
        NoLista noOrigem = this.obterNo(idNoOrigem);
        if (noOrigem != null) {
            ret = noOrigem.removeAresta(idNoDestino);
        }
        noOrigem = null;
        return ret;
    }
    @Override
    public boolean excluirTodasArestas(int idNo) {
        /* verifica se existe aresta */
        boolean ret = false;
        NoLista noOrigem = this.obterNo(idNo);
        if (noOrigem != null) {
            ret = noOrigem.removeAllAresta();
        }
        return ret;
    }
    
    public void imprimirNosVizinhos(int idNo) {
        int i = this.obterIndiceNo(idNo);
        super.imprimir();
        if (i != - 1 && vertices[i] != null)
             vertices[i].imprimir();
    }
    @Override
    public void imprimir() {
        int i;
        super.imprimir();
        for (i = 0; i < this.vertices.length; i++)
        {
          if (vertices[i] != null)
             vertices[i].imprimir();
        }
    }

    /* Obtem o Id do nó Origem,, ou seja o nó que não é destino de nenhum outro nó */
    public int obterIDNoOrigem()
    {
       int i, j, id = -1;
       for (i = 0; i < this.vertices.length; i++)
       {
         if (vertices[i] != null)
         {
           for (j = 0; j < this.vertices.length; j++)
           {
             /* Verifica se o Nó na posição i faz parte de alguma aresta como nó destino */
             if (vertices[j] != null && vertices[j].obterAresta(vertices[i].getId()) != null)
                break;
           }
           /* Não achou nenhuma aresta com nó destino de i, então ele é o nó origem */
           if (j == this.vertices.length)
           {
             id = vertices[i].getId();
             break;
           }
         }
       }
       return id;
    }

    /* Obtem o Id do nó Destino, ou seja o nó que não é origem de nenhum outro nó */
    public int obterIDNoDestino()
    {
       int i, id = -1;
       for (i = 0; i < this.vertices.length; i++)
       {
         /* Não possui nenhuma aresta, então ele é o nó Destino */
         if (this.vertices[i].getAresta() == null )
         {
            id = vertices[i].getId();
            break;
         }
       }
       return id;
    }

    /* Obtem o ID do primeiro nó do grafo */
    public int obterIDPrimeiroNo() {
        if (vertices != null && vertices.length >= 1)
            return vertices[0].getId();
        else
            return -1;
    }


    /* Retorna o id da primeira Aresta encontrada ou -1 senão existir aresta*/
    @Override
    public int obterIDPrimeiraAresta(int idNo) {
        int id = -1;
        NoLista no = this.obterNo(idNo);
        if (no != null) {
            id = no.getIDPrimeiraAresta();
        }
        return id;
    }


    /* Retorna o id da próxima Aresta encontrada ou -1 senão existir aresta*/
    @Override
    public int obterIDProximaAresta(int idNoOrigem, int idNoDestino) {
        int id = -1;
        NoLista noOrigem = this.obterNo(idNoOrigem);
        if (noOrigem != null) {
            id = noOrigem.getIDProximaAresta(idNoDestino);
        }
        return id;
    }

    /* Retorna o rotulo da ligação ou null senão não existir aresta*/
    @Override
    public Object obterRotuloAresta(int idNoOrigem, int idNoDestino) {
        NoLista noOrigem = this.obterNo(idNoOrigem);
        if (noOrigem != null) {
          return noOrigem.getRotuloAresta(idNoDestino);
        }
        return null;
    }
    /* Obtem o ID de um determinado no a partir do valor Nó */
    public int obterIdPorValor(String valor)
    {
       int i = -1;
        /* Pesquisa o Valor do Nó */
        for (NoLista no : vertices) {
            if (no.getValor().equals(valor)) {
                i = no.getId();
                break;
            }
        }
        return i;
    }
    public boolean obterDadosArquivo(String arquivo)
    {
        boolean res = true;
        String linha;
        try
        {
          FileReader      fr = new FileReader(arquivo);
          BufferedReader  br = new BufferedReader(fr);
          String []nos;      /* vetor de nós, obtido a partir da 1ª linha do arquivo */
          String []arestas;  /* vetor de arestas, obtido a partir da 2ª linha do arquivo */
          /* Lê a primeira linha, contendo os nós */
          linha = br.readLine();
          if (linha != null)
          {
            nos =  linha.split(";");
            /* insere os nós */
            for(int i = 0; i < nos.length; i++)
            {
                if (!(nos[i].trim()).equals(""))
                  this.inserirNo(nos[i]);
            }
          }
          int indNoOrigem;
          /* Lê as arestas e inclui as mesmas no grafo */
          while ((linha = br.readLine()) != null)
          {
             arestas = linha.split(";");
             /* obtem o ID do nó de origem, a partir do valor do nó */
             indNoOrigem = (this.obterIdPorValor(arestas[0]));
             if (indNoOrigem != -1)
             {
                for(int i = 1; i < arestas.length; i++)
                {
                   /* Se o valor for 1, então é para criar a aresta */
                    if ((arestas[i].trim()).equals("1.0"))
                      this.inserirAresta(indNoOrigem, i);
                }
             }
          }
        }
        catch (Exception e)
        {
           System.out.println("Erro ao obter os dados do arquivo: " + e.getMessage());
           res = false;
        }
       return res;
    }

    public boolean obterDadosArquivoPesos(String arquivo)
    {
        boolean res = true;
        String linha;
        try
        {
          FileReader      fr = new FileReader(arquivo);
          BufferedReader  br = new BufferedReader(fr);
          String []dados;    /* vetor de copm os dados lidos do arquivo */
          String rotulo;
          int indOrigem, indDestino, peso;


          while ((linha = br.readLine()) != null)
          {
            dados =  linha.split(" ");
            if (dados[0].equals("N")) /* A linha refere-se a um Nó */
            {
               /* insere os nós */
               for(int i = 1; i < dados.length; i++)
               {
                  if (!(dados[i].trim()).equals(""))
                    this.inserirNo(dados[i]);
               }
            }
            else if (dados[0].equals("A")) /* A linha refere-se a uma Aresta */
            {
                  /* insere as arestas */
                  try
                  {
                     indOrigem  = Integer.parseInt(dados[1].trim());
                     indDestino = Integer.parseInt(dados[2].trim());
                     rotulo     = dados[3].trim();
                     peso       = Integer.parseInt(dados[4].trim());
                  }
                  catch(Exception e)
                  {
                     indOrigem  = -1;
                     indDestino = -1;
                     rotulo     = "";
                     peso       = 0;
                  }
                  /* adiciona a aresta ao grafo */
                  if (indOrigem > 0 && indOrigem < this.vertices.length && indDestino > 0 && indDestino < this.vertices.length)
                  {
                     this.inserirAresta(vertices[indOrigem].getId(), vertices[indDestino].getId(), rotulo, peso);
                  }
            }
          }
        }
        catch (Exception e)
        {
           System.out.println("Erro ao obter os dados do arquivo: " + e.getMessage());
           res = false;
        }
       return res;
    }

    public boolean gerarArquivoEstrutura(String arquivo)
    {
        boolean res = true;
        String linha="";
        try
        {
          FileWriter      fr = new FileWriter(arquivo);
          BufferedWriter  br = new BufferedWriter(fr);
          int indUltNo = 0;
          /* Lê os nós */
          for (int i = 0; i < vertices.length; i++ )
          {
             if (vertices[i] != null){
               indUltNo = i;
               linha += ";" + vertices[i].getValor();
              }
          }
          /* grava a primeira linha do arquivo com os nós */
          br.write(linha);
          NoLista no;
          /* Lê nó e verifica as conexões do mesmo */
          for (int i = 0; i < vertices.length; i++ )
          {
            no = vertices[i];
            if (no != null)
            {
                linha = no.getValor();
                for (int j = 0; j <= indUltNo; j++ )
                {
                   if ( no.obterAresta(j+1) != null )
                     linha += ";" + "1.0";
                   else
                     linha += ";" + "0";
                }
                /* grava linha de arestas do nó */
                br.write("\n");
                br.write(linha);
             }
          }
         br.close();
        }
        catch (Exception e)
        {
           System.out.println("Erro ao gravar os dados no arquivo: " + e.getMessage());
           res = false;
        }
       return res;
    }

    /**
     * @return os vertices
     */
    public ArrayList<No> obterVertices() {
        ArrayList <No> listaNo = new ArrayList<No>();
        for(int i = 0; i < vertices.length; i++)
            if (vertices[i] != null)
                listaNo.add(vertices[i]);
       return listaNo;
    }

    /**
     * @param vertices the vertices to set
     */
    public void setVertices(NoLista[] vertices) {
        this.vertices = vertices;
    }

    public No obterNoPorID(int idNo)
    {
       return this.obterNo(idNo);
    }


    public ArrayList<No> obterNosVizinhos(int idNo)
    {
       NoLista no = this.obterNo(idNo);
       if (no != null)
           return no.obterNosVizinhos();
       else
           return null;
    }

}
